package com.meterhuang;

import lombok.extern.slf4j.Slf4j;

/**
 * 最长回文数
 * 给你一个字符串 s，找到 s 中最长的回文子串
 * 参考：https://leetcode-cn.com/problems/longest-palindromic-substring/
 *
 * @author meterhuang
 * @date 2021/04/25 16:03
 */
@Slf4j
public class LongestPalindrome {

	public static final int HALF = 2;

	public static void main(String[] args) {
		String str = "1222221";
		String longestPalindrome = longestPalindrome(str);
		log.info("longest palindrome: {}", longestPalindrome);
		longestPalindrome = longestPalindromeV2(str);
		log.info("longest palindrome: {}", longestPalindrome);
	}

	/**
	 * 是否回文数
	 * @param s
	 * @return
	 */
	public static boolean isPalindrome(String s) {
		int length = s.length();
		for (int i = 0; i < length / HALF; ++i) {
			if (s.charAt(i) != s.charAt(length - i - 1)) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 暴力解法：耗时，因为超时无法AC
	 * @param s
	 * @return
	 */
	public static String longestPalindrome(String s) {
		int max = 0;
		String palindrome = "";
		int length = s.length();
		for (int i = 0; i < length; ++i) {
			// j == length是因为substring的第二个参数不包含end所在字符
			for (int j = i + 1; j <= length; ++j) {
				String substring = s.substring(i, j);
				if (substring.length() > max && isPalindrome(substring)) {
					max = substring.length();
					palindrome = substring;
				}
			}
		}

		return palindrome;
	}

	/**
	 * 动态规划： P(i,j)=P(i+1,j−1)∧(Si==Sj)
	 * @param s
	 * @return
	 */
	public static String longestPalindromeV2(String s) {
		int len = s.length();
		if (len < HALF) {
			return s;
		}
		int maxLen = 1;
		int begin = 0;
		// dp[i][j]表示si->sj是否是回文子串
		boolean[][] dp = new boolean[len][len];
		for (int i = 0; i < len; ++i) {
			dp[i][i] = true;
		}

		char[] charArray = s.toCharArray();
		for (int LEN = 2; LEN <= len; ++LEN) {
			for (int i = 0; i < len; ++i) {
				int j = LEN + i - 1;
				if (j >= len) {
					break;
				}
				if (charArray[j] != charArray[i]) {
					dp[i][j] = false;
				} else {
					//1 2 1
					//0 1 2 => 2 - 0 = 2,中间只有一位，故当j - i < 3则一定是回文
					if (j - i < 3) {
						dp[i][j] = true;
					} else {
						dp[i][j] = dp[i + 1][j - 1];
					}
				}

				// 长度大于maxLen,且是回文子串
				if (dp[i][j] && j - i + 1 > maxLen) {
					maxLen = j - i + 1;
					begin = i;
				}
			}
		}

		return s.substring(begin, begin + maxLen);
	}

}
